/*
 * Lab6B.cpp
 *
 *  Created on: 2011-04-22
 *      Author: A Varghese
 */

#include <iostream>

class Tree{
public:
	Tree(): root(NULL){}
	~Tree(){ delete_postorder(root);}
	void add(int d){
		if (root==NULL)
			root = new Node(d);
		else
			add_inorder(root, d);
	}
	friend std::ostream& operator <<( std::ostream& o, Tree& t){
		o << "Inorder traversal:   ";
		t.print_inorder(o, t.root);
		o << std::endl;
		return o;
	}
	void convert_to_list(std::ostream& o){
		list->destroy();
		list = NULL;
		list = list_inorder( root );
		/*
		 * Print list
		 */
		for (LNode* p = list; p != NULL; p=p->next)
			o << p->data << " ";
		o << std::endl;
	}
private:
	class Node{
	public:
		Node(int d): data(d){left=right=NULL;}
		int data;	Node* left;  Node* right;
	};
	Node* root;

	void add_inorder(Node* t, int d){
		if (d <= t->data)
			if (t->left == NULL)
				t->left = new Node(d);
			else add_inorder(t->left, d);
		else
			if (t->right == NULL)
				t->right = new Node(d);
			else add_inorder(t->right, d);
	}

	void print_inorder(std::ostream& o, Node*t){
		if (t==NULL) return;
		print_inorder(o, t->left);
		o << t->data << " ";
		print_inorder(o, t->right);
	}
	void delete_postorder(Node* t){
		if (t== NULL) return;
		delete_postorder( t->left );  t->left = NULL;
		delete_postorder( t->right ); t->right = NULL;
		delete t;
	}
	class LNode{
	public:
		LNode(int d): data(d){next=NULL;}
		int data;
		LNode* next;
		void append(int d){
			LNode* p = this;
			for (; p->next != NULL; p=p->next) ;
			p->next = new LNode( d );
		}
		void destroy(){
			// delete all the nodes in the linked list
		}
	};

	LNode* list;
	LNode* list_inorder(Node* t){
		if (t==NULL) return NULL;
		LNode* left = list_inorder( t-> left );
		LNode* right = list_inorder( t->right );
		if (left == NULL) return right;
		if (right == NULL) return left;
		/*
		 * Find last node in "left" and append right to it.
		 */
		LNode* p = left;
		for (; p->next != NULL; p=p->next) ;
		p->next = right;

		return left;
	}

/*	void list_inorder(Node* t){
		if (t==NULL) return;
		list_inorder( t-> left );
		if (list==NULL)
			list = new LNode( t->data );
		else
			list->append(t->data);
		list_inorder( t->right );
	}
*/
};



int main(){
	Tree t;
	int data[] = { -2, 3, 10, -21, 35, 3, 85, -2, 100};

	for (int i=0; i<9; i++)
		t.add( data[i] );

	std::cout << t << std::endl;

	t.convert_to_list( std::cout );

	std::cout << "Done!";
}
